package dp;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 斐波那契数509.java
 * @Description https://leetcode-cn.com/problems/fibonacci-number/
 * @createTime 2021年11月29日 21:01:00
 */
public class 斐波那契数509 {
	public int fib(int n) {
		if (n<2){
			return n;
		}
		int fn1=0,fn2=0,fn=1;
		for (int i = 2; i <= n; i++) {
			fn1=fn2;
			fn2=fn;
			fn=fn1+fn2;
		}
		return fn;
	}


	public int fib2(int n) {
		if (n<2){
			return n;
		}
		int[] dp=new int[n+1];
		dp[0]=0;
		dp[1]=1;
		for (int i = 2; i <= n; i++) {
			dp[i]=dp[i-1]+dp[i-2];
		}
		return dp[n];
	}
}
